package map;

public class BinarySearchTree {
    static TreeNode root = null;
    //查找
    public boolean search(int val){
        TreeNode cur = root;
        while(cur!=null){
            if(cur.val>val){
                 cur = cur.left;
            }else if(cur.val<val){
                cur = cur.right;
            }else {
                return true;
            }
        }
        return false;
    }

    //插入
    public static boolean insert(int val){
        TreeNode val1 =new TreeNode(val);
        if(root ==null){
            root =val1;
            return true;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur!=null){
            if(cur.val>val){
                parent = cur;
                cur =cur.left;
            }else if(cur.val<val){
                parent = cur;
                cur = cur.right;
            }else {
                return false ;
            }
        }
        if(parent.val<val){
            parent.right = val1;
        }else {
            parent.left = val1;
        }
        return true;
    }

    //删除
    public static void remove(int val){
        if(root == null){
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur!=null){
            if(cur.val>val){
                parent = cur;
                cur =cur.left;
            }else if(cur.val<val){
                parent = cur;
                cur = cur.right;
            }else {
                //删除操作
                removeNode(cur,parent);
            }
        }
    }

    public static void removeNode(TreeNode cur,TreeNode parent){
        if(cur.left==null){
            if(cur==root){
                root = root.right;
            } else if (cur == parent.right) {
                parent.right = cur.right;
            }else if(cur == parent.left){
                parent.left = cur.right;
            }
        }else if(cur.right ==null){
            if(cur==root){
                root = root.left;
            }else if(cur ==parent.left){
                parent.left = cur.left;
            }else if(cur ==parent.right){
                parent.right = cur.left;
            }
        }else{
            //替罪羊法：找到左子树的最右边节点或者找到右子树的最左边节点
            TreeNode tmp1 = cur;
            TreeNode tmp2 =cur.right;
            while(tmp2.left!=null){
                tmp1 = tmp2;
                tmp2 = tmp2.left;
            }
            cur.val = tmp2.val;

            if(tmp2 ==tmp1.left){
                tmp1.left =tmp2.right;
            }else if(tmp2 ==tmp1.right){
                tmp1.right = tmp2.right;
            }

        }
    }


    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(5);
        binarySearchTree.insert(1);
        binarySearchTree.insert(7);
        binarySearchTree.insert(9);

    }

}
